HW#1 --- last modified February 28 2019 22:25:23..

Solution set.

Due date: Feb 16

Files to be submitted:
  Hw1.zip

Purpose: To learn about the history of each of the computational paradigms we will consider this semester. To gain experience with a procedural programming language, C. To learn about the steps in the compilation process, as well as the GNU compiler tools.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Have a basic knowledge of the history of programming languages.

LO2 -- Have a basic knowledge of the procedural, object-oriented, functional, and logic programming paradigms.

LO3 -- Understand the roles of interpreters, compilers, and virtual machines.

Specification:

For this assignment, you will submit all your files in the ZIP file Hw1.zip. In this file make sure to have a file readme.txt which lists each group member that participated in this project. There are two parts of this assignment: a written part and a coding/experiment part. The written part should be in a file history.txt in your ZIP file. For the written part of the assignment, I want you to write a couple of paragraphs on the history of each of the following programming language features: (a) regular expressions, (b) iterators/generators, (c) object inheritance, (d) garbage collection. For each try to find the earliest language which directly supported the feature, find a modern language which supports the feature, and discuss how the feature has evolved between the two languages. Make sure to properly reference your sources, and if possible actually try to check out a book or two rather than just rely on the internet.

For the coding part of the assignment, first you will create a typedef struct called Expression for holding expressions, and a function which can evaluate expressions built using your struct. This struct will have three components a Data typedef union type, and two pointers to Expression's leftArgument and rightArgument. The Data union type contains either a Operation typedef enum or an int. An Operation enum can be one of MULT, ADD, CURR_POWER, or POWER. The idea is Expression's can be used to represent things like:

7⁴*(4+5)

where MULT is used to handle *, ADD is used to handle +, and exponents like 7⁴ are handled using POWER. Numbers are represented by expressions where the leftArgument and rightArgument are both null and Data is being used to contain an int. CURR_POWER is used to raise an int to whatever is the value of the global int variable curr_pow, its right argument is null.

Put the definitions of Expression, Data, Operation in the header file expressions.h . Create three files test1.h, test2.h, test3.h, each should have one Expression tree in it (a global variable declaration Expression tree = ...; ) built out of Expression's and making use of each of the four operations.

You should have a file evaluator.c which contains a function of prototype:

int eval(Expression E);

which calculates the int value of the supplied expression. This file should also contain a recursive function of prototype:

int power(int x, int y);

for computing powers. Finally, you will create a program driver.c which has the main function. You should have a Makefile with targets test1, test2, test3, all, and clean. (all makes each of test1, test2, and test3, clean gets rid of any intermediary files). The grader will switch into your Hw1 folder after unzipping Hw1.zip, and delete any executables. Then the grader will type:

make test1

to run the first test1. Similarly, for each of the other tests. Next,

./test1 some_number

will be typed. some_number might be 2, 3, etc. This should cause the main function in driver.c to be called. curr_pow should be set to some_number, as make test1 was used, test1.h should have been included into driver.c (similarly, if make test2 was called test2.h should have been included, etc). The function main should call eval(tree) and then write the output to the file output.txt .

The next requirement for this project is that each of the make targets test1, test2, test3 depends on sub-targets for each of the stages of the compilation phase test1. By default, if you type "gcc myfile.c" it runs the preprocessor, compiles this, and then links the result. Instead, you should have targets like: preprocesstest1 which uses gcc's -E flag to output the result of just the preprocessor; compiletest1 which uses the -S flag to compile the result to assembly; assembletest1, which uses the as command to produce object code; and linktest1 which uses ld to link the objects code together. So that you have actually looked at what each phase outputs, after you are done your project above type, "make compiletest1", copy the file evaluator.s to experiment.s. Find where in the assembly that the addition of expressions is done and change that operation to a multiplication. Assemble and link the result. Leave experiment.s in your zip for the grader to look at. The point here is just to make you look at the kind of code (mod converting to bits, dealing with symbols, and linking) that your computer really runs on. You don't need to understand much assembly to do this (imul is the instruction for multliplication).

For the last part of this assignment, I want you to test out the gdb debugger. Use the script command (type "man script" to find out how it works), to create a file debug.log of your experiments. Have a make target test1simple (you don't need to do this for test2 or test3) which rather than split the compilation of test1 into the steps above does just runs gcc on the necessary source files with the -g (debug) flag. Then type "gdb test1simple", list the program, set a breakpoint, run the program, use "step" at least once, use "next" at least once, "print" the value of a variable, "clear" a breakpoint, and quit.

Point Breakdown